// 给定一个已经从小到大排序的数组和一个目标数字，
// 在数组中使用二分查找算法查找目标数字的索引，若不存在则返回 -1
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const target = 3; //查找数字7
let left = 0; //最左边的下标
let right = arr.length - 1; //最右边的下标
let res = -1;
let mid;
while (left <= right) {
  mid = Math.floor((left + right) / 2); //找到中间的下标
  if (arr[mid] === target) {
    res = mid;
    break;
  } else if (target > arr[mid]) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
console.log(res);
// 5<7==右边
// console.log(res); // 6
// 0,1,2,3,4,5,6,7,8
// 10000000
// 9999999
// for(0-10000000)
// if(i==9999999)
// //5000000 《》9999999   中间右边
// 10

// 9

// 10/2 = 5
// 9<>5
// 右边
// 1,2,3,4,5,6,7,8,9,10
// 6,7,8,9,10
// 8<>9
// 右边
// 9,10
// 2/2=1
// 10<>9
// 左边
// 9<>9

// 100 99

// 二分查找 也叫做折半查找对半查找
// 先确定中间下标
// 然后和目标值对比
// 看是否相等
// 和谁大谁小
// 目标值比中间大说明在右边
// 需要确定右边的下标范围
// 反之就是在左边需要确定左边的下标范围
// 如何确定左边和右边的下标范围
// 有中间值下标 右边： 用右边的范围就是中间下标+1~最后一位下标
//             左边：0~中间下标-1
// 以此类推找到目标值
